package algorithm.Sort;

import java.util.Arrays;

/**
 * @program:Algorithm
 * @description:堆排序算法
 * @author:Lance
 * @create:2020-09-15 20:18
 **/
public class HeapSort {
    public static void main(String[] args) {
        int [] arr = {2,3,8,1,4,9,10,7,16,14};
        HeapSort(arr, arr.length);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 堆排序
     * 堆：1.完全二叉树（自上而下，自左而右）2.每一个子树上父节点一定要大于子节点
     * @param arr
     */
    public static void HeapSort(int[] arr,int n){
        //建堆
        for (int i = n/2-1; i >=0 ; i--) {
            heapify(arr, n, i);
        }
        //排序
        for (int i = n-1; i >0 ; i--) {
            int temp = arr[i];
            arr[i]  = arr[0];
            arr[0] = temp;
            heapify(arr, i, 0);
        }
        
    }

    /**
     * heapify(堆化):从父节点和左右孩子中选出最大值和父节点进行交换，直到叶子节点交换完毕完成heapify
     * 如果是一个完全混序树，要从h-1层（倒数第二层）进行heapify
     * 将一个完全二叉树进行一维数组化
     * 对于任意一个子节点i，其父节点是(i-1)/2，其左孩子是2i+1,右孩子是2i+2
     * @param tree
     * @param n  节点数
     * @param i  对某个节点进行heapify
     */
    public static void heapify(int[] tree, int n, int i){
       int c1 = 2*i+1;
       int c2 = 2*i+2;
       int max = i;
       if(c1<n&&tree[c1]>tree[max]){
           max = c1;
       }
       if(c2<n&&tree[c2]>tree[max]){
           max = c2;
       }if(max!=i){
           //如果max!=i说明存在子节点比父节点大的情况，那么就需要交换
            int temp = tree[max];
            tree[max] = tree[i];
            tree[i] = temp;
            heapify(tree,n,max);
        }
    }

}
